import java.util.Arrays;

public class TestHeap {
    public int[] elem;
    public int usedSize;

    public TestHeap() {
        //初始话
        this.elem = new int[10];
    }

    public void initElem(int[] array) {
        //把elem里的值设置为我们输入的值
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
        }
    }



    /**
     * 建堆的时间复杂度为O(N)。
     * 大根堆
     * @param parent 每颗子树调整时候的起始位置
     * @param usedSize 用来判断 每颗子树什么时候结束的
     */
    private void shiftDown(int parent,int usedSize) {
        int child = parent * 2 + 1;//parent根节点的左子树的节点

        while (child < usedSize) {

            //判断有没有右子树，如果有就把 child 设置为最大的值的下标
            if (child + 1 < usedSize && elem[child + 1] > elem[child]) {
                //右子树比左子树大把 child + 1，就是右子树
                child += 1;
            }

            if (elem[parent] < elem[child]) {
                //进行交换
                swap(elem,child,parent);
                //调整完，把 parent 和 child 进行调整位置
                parent = child;
                child = parent * 2 + 1;
            }else {
                //这是 parent下标的值大于child，跳出
                break;
            }
        }
    }

    private void swap(int[] elem,int i,int j) {
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }

    //大根堆的创建
    public void createHeap() {
        for (int parent = (this.usedSize - 1 - 1) / 2; parent >= 0 ; parent--) {
            shiftDown(parent,this.usedSize);
        }
    }

    //堆的插入
    public void offer(int val) {
        if (isFull()) {
            //满了。2倍扩容
            this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
        }

        //插入操作
        this.elem[usedSize] = val;
        //这个时候 usedSize 位置就是我们的子树的坐标位置
        shiftUp(usedSize);
        this.usedSize++;
    }

    private void shiftUp(int child) {
        int parent = (child - 1) / 2;
        while (parent >= 0) {
            //进行向上调整
            if (this.elem[parent] < this.elem[child]) {
                //交换
                swap(elem,child,parent);
                //parent 和 child 调整位置
                child = parent;
                parent = (child - 1) / 2;
            }
            else {
                break;
            }
        }
    }

    //堆的删除操作
    public int poll() {
        //删除优先级最高的就是0下标的值，有三个步骤：
        //1、把堆的第一个数据和最后一个数据进行交换
        //2、把有效数据长度进行减1
        //3、把 0 下标的值进行向下调整
        if (isEmpty()) {
            //堆为空，结束
            return -1;
        }

        int val = elem[0];
        //1、
        swap(elem,0,usedSize - 1);
        //2、
        usedSize--;
        //3、
        shiftDown(0,usedSize);

        return val;
    }

    //返回堆顶的数据
    public int peek() {
        if (isEmpty()) {
            return -1;
        }

        return this.elem[0];
    }

    //判空
    public boolean isEmpty() {
        return usedSize == 0;
    }

    //判满
    public boolean isFull() {
        return usedSize == this.elem.length;
    }

    //堆排序
    //升序 -> 创建大根堆
    //降序 -> 创建小根堆
    //这里我们是创建的大根堆，我们来看看升序
    public void HeapSort() {
        //我们把第一个数据和最后一个数据进行交换
        //之后我们把 0 下标的值进行向下排序，这样之后我们会把大值放后面，小值放堆的前面
        int end = usedSize - 1;
        while (end > 0){
          swap(elem,0,end);
          shiftDown(0,end);
          end--;
        }
    }
}
